﻿using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using ParserGenerator.Collections;
using ParserGenerator.DataStructures;
using ParserGenerator.Exceptions;
using ParserGenerator.Extensions;
using ParserGenerator.GrammarAnalysis;
using ParserGenerator.Input;
using ParserGenerator.SyntacticAnalysis;

namespace ParserGenerator.GrammarConstruction
{
    [Serializable]
    public sealed class GrammarNonterminalTable : ReadOnlyCollection<GrammarNonterminalSymbol>
    {
        public FreshNameGenerator NameGenerator { get; }

        [NonSerialized]
        private ReadOnlyDictionary<string, GrammarNonterminalSymbol> _startNonterminalsWrapper;
        private readonly Dictionary<string, GrammarNonterminalSymbol> _startNonterminals;
        public ReadOnlyDictionary<string, GrammarNonterminalSymbol> StartNonterminals
        {
            get
            {
                if (_startNonterminalsWrapper == null)
                    _startNonterminalsWrapper = _startNonterminals.AsReadOnly();
                return _startNonterminalsWrapper;
            }
        }

        [NonSerialized]
        private ReadOnlyDictionary<string, GrammarNonterminalSymbol> _userNonterminalsWrapper;
        private readonly Dictionary<string, GrammarNonterminalSymbol> _userNonterminals;
        public ReadOnlyDictionary<string, GrammarNonterminalSymbol> UserNonterminals
        {
            get
            {
                if (_userNonterminalsWrapper == null)
                    _userNonterminalsWrapper = _userNonterminals.AsReadOnly();
                return _userNonterminalsWrapper;
            }
        }

        [NonSerialized]
        private ReadOnlyDictionary<string, GrammarNonterminalSymbol> _autoDefinedNonterminalsWrapper;
        private readonly Dictionary<string, GrammarNonterminalSymbol> _autoDefinedNonterminals;
        public ReadOnlyDictionary<string, GrammarNonterminalSymbol> AutoDefinedNonterminals
        {
            get
            {
                if (_autoDefinedNonterminalsWrapper == null)
                    _autoDefinedNonterminalsWrapper = _autoDefinedNonterminals.AsReadOnly();
                return _autoDefinedNonterminalsWrapper;
            }
        }

        public GrammarDeclaration Grammar { get; }
        public GrammarTerminalTable Tokens { get; }
        public GrammarGoalDescriptorTable Goals { get; }
        public GrammarProductionTable Productions { get; }

        internal GrammarNonterminalTable(GrammarDeclaration grammar, GrammarTerminalTable tokens)
            : base(new List<GrammarNonterminalSymbol>())
        {
            if (grammar == null)
                throw new ArgumentNullException(nameof(grammar));
            if (tokens == null)
                throw new ArgumentNullException(nameof(tokens));
            NameGenerator = new FreshNameGenerator(tokens.NamedTokens.Keys);
            Grammar = grammar;
            Tokens = tokens;
            _startNonterminals = new Dictionary<string, GrammarNonterminalSymbol>();
            _userNonterminals = new Dictionary<string, GrammarNonterminalSymbol>();
            _autoDefinedNonterminals = new Dictionary<string, GrammarNonterminalSymbol>();
            Define(grammar.SyntacticDeclaration, tokens);
            Goals = new GrammarGoalDescriptorTable();
            Productions = new GrammarProductionTable();
            if (!AnyGoalDefined(grammar) && Count > 0)
            {
                GrammarNonterminalSymbol sym = this[0];
                Identifier name = Identifier.New(sym.Name, sym.Context);
                GoalDeclarator goal = GoalDeclarator.New(name, Sequence.GetEmpty<TokenReference>());
                GoalDeclaration decl = GoalDeclaration.New(Sequence.Create(goal));
                Goals.Define(decl, tokens, this, Productions);
            }
            foreach (Directive d in grammar.Directives.Items)
                if (d.IsGoal)
                    Goals.Define(d.AsGoal.Declaration, tokens, this, Productions);
            SyntacticExpressionReducer reducer = new SyntacticExpressionReducer(this);
            reducer.DefineProductions(grammar.SyntacticDeclaration);
            ComputeNullability();
            ComputeFirstSets();
            ComputeFollowSets();
            ComputeDerives();
        }

        private static bool AnyGoalDefined(GrammarDeclaration grammar)
        {
            if (grammar == null)
                throw new ArgumentNullException(nameof(grammar));
            foreach (Directive d in grammar.Directives.Items)
                if (d.IsGoal && d.AsGoal.Declaration.Items.Count > 0)
                    return true;
            return false;
        }

        private void Define(SyntacticDeclaration n, GrammarTerminalTable tokens)
        {
            if (n == null)
                throw new ArgumentNullException(nameof(n));
            if (tokens == null)
                throw new ArgumentNullException(nameof(tokens));
            foreach (SyntacticDeclarator decl in n.Declarators)
            {
                GrammarNonterminalSymbol sym;
                if (_userNonterminals.TryGetValue(decl.Name.Name, out sym))
                {
                    string message = string.Format(SR.NamedNonterminalDefined, decl.Name.Name.AsSingleQuote());
                    NameErrorException e = new NameErrorException(message);
                    e.AddLocation(sym.Context);
                    e.AddLocation(decl.Name.Context);
                    throw e;
                }
                GrammarTerminalSymbol token;
                if (tokens.NamedTokens.TryGetValue(decl.Name.Name, out token))
                {
                    string message = string.Format(SR.NonterminalDefinedAsTerminal, decl.Name.Name.AsSingleQuote());
                    NameErrorException e = new NameErrorException(message);
                    e.AddLocation(sym.Context);
                    e.AddLocation(decl.Name.Context);
                    throw e;
                }
                sym = new GrammarNonterminalSymbol();
                sym.Number = Items.Count;
                sym.Name = decl.Name.Name;
                sym.Context = decl.Name.Context;
                sym.HasSimpleName = true;
                _userNonterminals.Add(decl.Name.Name, sym);
                Items.Add(sym);
                NameGenerator.UseName(sym.Name);
                sym.Type = decl.Type;
            }
        }

        internal GrammarNonterminalSymbol DefineStart(GrammarNonterminalSymbol goal, SourceContext context)
        {
            if (goal == null)
                throw new ArgumentNullException(nameof(goal));
            string name = NameGenerator.GetFreshName(goal.Name);
            GrammarNonterminalSymbol sym = new GrammarNonterminalSymbol();
            sym.Number = Items.Count;
            sym.Name = name;
            sym.Context = context;
            sym.IsAutoDefined = true;
            _startNonterminals.Add(name, sym);
            Items.Add(sym);
            NameGenerator.UseName(sym.Name);
            return sym;
        }

        internal GrammarNonterminalSymbol DefineUnnamed(string text, string hint)
        {
            if (text == null)
                throw new ArgumentNullException(nameof(text));
            if (hint == null)
                throw new ArgumentNullException(nameof(hint));
            GrammarNonterminalSymbol sym;
            if (_autoDefinedNonterminals.TryGetValue(text, out sym))
            {
                string message = string.Format(SR.UnnamedNonterminalDefined, text);
                NameErrorException e = new NameErrorException(message);
                e.AddLocation(sym.Context);
                throw e;
            }
            string name = NameGenerator.GetFreshName(hint);
            sym = new GrammarNonterminalSymbol();
            sym.Number = Items.Count;
            sym.Name = name;
            sym.IsAutoDefined = true;
            _autoDefinedNonterminals.Add(text, sym);
            Items.Add(sym);
            NameGenerator.UseName(sym.Name);
            return sym;
        }

        public GrammarNonterminalSymbol LookupNamed(Identifier name)
        {
            if (name == null)
                throw new ArgumentNullException(nameof(name));
            GrammarNonterminalSymbol sym;
            if (!_userNonterminals.TryGetValue(name.Name, out sym))
            {
                string message = string.Format(SR.NonterminalNotDefined, name.Name.AsSingleQuote());
                NameErrorException e = new NameErrorException(message);
                e.AddLocation(name.Context);
                throw e;
            }
            return sym;
        }

        private void ComputeNullability()
        {
            var nullable = new HashSet<GrammarNonterminalSymbol>();
            var queue = new Queue<GrammarNonterminalSymbol>();
            var propagate = new Dictionary<GrammarNonterminalSymbol, List<GrammarProduction>>();
            var counting = new Dictionary<GrammarProduction, int>();
            foreach (GrammarNonterminalSymbol owner in Items)
            {
                foreach (GrammarProduction prod in owner.Productions)
                {
                    if (prod.IsEmpty)
                    {
                        if (nullable.Add(owner))
                            queue.Enqueue(owner);
                    }
                    else if (prod.NoTokens)
                    {
                        foreach (GrammarSymbol sym in prod.Symbols)
                            propagate.AddValueItem(sym.AsNonterminal, prod);
                        counting[prod] = prod.Length;
                    }
                }
            }
            while (queue.Count > 0)
            {
                GrammarNonterminalSymbol n = queue.Dequeue();
                List<GrammarProduction> list;
                if (!propagate.TryGetValue(n, out list))
                    continue;
                foreach (GrammarProduction prod in list)
                    if (--counting[prod] == 0)
                        if (nullable.Add(prod.Owner))
                            queue.Enqueue(prod.Owner);
            }
            foreach (GrammarNonterminalSymbol n in nullable)
                n.Nullable = true;
        }

        private void ComputeFirstSets()
        {
            var firstSets = new Dictionary<GrammarNonterminalSymbol, HashSet<GrammarTerminalSymbol>>();
            var relation = new BinaryRelation<GrammarNonterminalSymbol>();
            foreach (GrammarNonterminalSymbol owner in Items)
            {
                foreach (GrammarProduction prod in owner.Productions)
                {
                    foreach (GrammarSymbol sym in prod.Symbols)
                    {
                        if (sym.IsTerminal)
                        {
                            firstSets.AddValueItem(owner, sym.AsTerminal);
                            break;
                        }
                        else
                        {
                            relation.Add(owner, sym.AsNonterminal);
                            if (!sym.AsNonterminal.Nullable)
                                break;
                        }
                    }
                }
            }
            relation.TransitiveClosure(firstSets);
            foreach (GrammarNonterminalSymbol owner in Items)
                owner.FirstSet = firstSets.TryGetValueOrCreate(owner).AsReadOnly();
        }

        private void ComputeFollowSets()
        {
            var followSets = new Dictionary<GrammarNonterminalSymbol, HashSet<GrammarTerminalSymbol>>();
            var relation = new BinaryRelation<GrammarNonterminalSymbol>();
            foreach (GrammarNonterminalSymbol owner in Items)
            {
                foreach (GrammarProduction prod in owner.Productions)
                {
                    int index = 0;
                    foreach (GrammarSymbol sym in prod.Symbols)
                    {
                        index++;
                        if (sym.IsNonterminal)
                        {
                            followSets.AddValueItems(sym.AsNonterminal, prod.FirstSet(index));
                            if (prod.Nullable(index))
                                relation.Add(sym.AsNonterminal, owner);
                        }
                    }
                }
            }
            relation.TransitiveClosure(followSets);
            foreach (GrammarNonterminalSymbol owner in Items)
                owner.FollowSet = followSets.TryGetValueOrCreate(owner).AsReadOnly();
        }

        private void ComputeDerives()
        {
            var relation = new BinaryRelation<GrammarNonterminalSymbol>();
            var firsts = new Dictionary<GrammarNonterminalSymbol, HashSet<GrammarNonterminalSymbol>>();
            foreach (GrammarNonterminalSymbol owner in Items)
            {
                var set = new HashSet<GrammarNonterminalSymbol>() { owner };
                firsts.Add(owner, set);
                foreach (GrammarProduction prod in owner.Productions)
                {
                    if (!prod.IsEmpty && prod.Symbols[0].IsNonterminal)
                    {
                        relation.Add(owner, prod.Symbols[0].AsNonterminal);
                        set.Add(prod.Symbols[0].AsNonterminal);
                    }
                }
            }
            relation.TransitiveClosure(firsts);
            foreach (GrammarNonterminalSymbol owner in Items)
            {
                var prods = new List<GrammarProduction>();
                foreach (GrammarNonterminalSymbol target in firsts[owner])
                    prods.AddRange(target.Productions);
                owner.Derives = prods.ToArray().AsReadOnly();
            }
        }

        public sealed override string ToString()
        {
            return string.Join("\n", Items);
        }
    }
}
